package java_0228;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.NoSuchElementException;

/**
 * 基于整形的最大堆实现
 * 根节点从0开始编号
 * 若此时节点编号为k，左子树编号2k+1,右子树2k+2,父结点编号：(k-1)>>2
 */
public class MaxHeap {
    //使用JDK内部动态数组
    List<Integer> data;
    public MaxHeap() {
        this(10);
    }
    //初始化堆大小
    public MaxHeap(int size) {
        data = new ArrayList<>(size);
    }
    public boolean isEmpty(){
        return data.size()==0;
    }
    //根据索引得到父节点索引
    private int parent(int k){
        return (k-1)>>1;
    }
    //根据索引得到左右子树索引
    private int left(int k){
        return 1+(k<<1);
    }
    private int right(int k){
        return 2+(k<<1);
    }
    /**
     * 1.向最大堆添加一个元素val
     * @return
     */
    public void add(int val){
        //1.尾部添加元素（List集合的add方法默认就是尾插）
        data.add(val);
        //2.进行元素上浮操作。最后一个元素的索引：data.size()-1
        siftUp(data.size()-1);
    }

    /**
     * 元素上浮操作
     * @param k
     */
    private void siftUp(int k) {
        //索引为k的元素进行上浮
        //上浮终止条件:已经走到根节点或当前节点值<=父节点值
        //则循环迭代条件：还存在父节点并且当前节点值>父节点值
        while(k>0&&data.get(k)>data.get(parent(k))){
            //交换当前节点与父节点值
            swap(k,parent(k));
            //k继续向上攀登
            k=parent(k);
        }
    }

    /**
     * 交换两个索引位置的值
     * @param i
     * @param j
     */
    private void swap(int i, int j) {
        int temp=data.get(i);
        data.set(i,data.get(j));
        data.set(j,temp);
    }

    /**
     * 2.取出当前最大堆的最大值
     * @return
     */
    public int extractMax(){
        //取值注意判空
        if(isEmpty()){
            throw new NoSuchElementException("heap is empty, can not extract");
        }
        //最大值就在堆顶，取出，最后return就行
        int max=data.get(0);
        //取出最大值后的操作（取出最大值后新的堆的合并情况）
        //1.数组末尾元素顶到堆顶-把索引为0位置元素值（堆顶）变为末尾元素值
        //set(int index,新值):修改index位置元素为新元素，返回修改前的元素值
        int lastVal=data.get(data.size()-1);
        data.set(0,lastVal);
        //2.将数组末尾元素删除
        data.remove(data.size()-1);
        //3.元素下沉操作
        siftDown(0);
        return max;
    }

    /**
     * 元素的下沉操作
     * @param k
     */
    private void siftDown(int k) {
        //终止条件：还存在子树时
        while(left(k)< data.size()){
            //j为左子树的索引
            int j=left(k);
            //判断是否有右子树
            if(j+1<data.size()&&data.get(j+1)>data.get(j)){
                //此时存在右子树并且右子树值比左子树的值大
                //给j+1让他成为右子树的索引
                j=j+1;
            }
            //此时j对应左右子树最大值的索引
            //和当前节点k去比较
            if(data.get(k)>=data.get(j)){
                //k索引对应的节点值>左右节点的最大值，下沉结束
                break;
            }else{
                //小于，交换k,j对应节点值，并让左右孩子的索引j的值赋值给k，k继续向下遍历
                swap(k,j);
                k=j;
            }
        }
    }

    /**
     * 将任意数组堆化
     * @param arr
     */
    public MaxHeap(int[] arr){//也是个构造方法
        data=new ArrayList<>(arr.length);//初始化
        //1.先将arr所有元素复制到data数组中（注意不是堆的添加，只是把所有元素放到data数组中）
        for (int i:arr) {
            data.add(i);
        }
        //2.从最后一个非叶子节点（最后一个叶子节点的父节点）开始siftDown(下沉)
        for (int i = parent(data.size()-1); i >= 0 ; i--) {
            siftDown(i);
        }
    }

    @Override
    public String toString() {
        return data.toString();
    }
}
